import java.util.Arrays;
import java.util.TreeMap;

public class Solution1425 {
    public int constrainedSubsetSum(int[] nums, int k) {
        int[] f=new int[nums.length];
        TreeMap<Integer,Integer> treeMap=new TreeMap<>();
        for (int i=0;i<nums.length;i++){
            int max=treeMap.isEmpty()?0:Math.max(0,treeMap.lastKey());
            f[i]=nums[i]+max;
            treeMap.put(f[i],treeMap.getOrDefault(f[i],0)+1);
            if (i>=k){
                treeMap.put(f[i-k],treeMap.get(f[i-k])-1);
                if (treeMap.get(f[i-k])==0){
                    treeMap.remove(f[i-k]);
                }
            }
        }
        return Arrays.stream(f).max().getAsInt();
    }

    public static void main(String[] args) {
        System.out.println(new Solution1425().constrainedSubsetSum(new int[]{10,-2,-10,-5,20},2));
    }
}
